//在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。 
//
// 请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。 
//
// 
//
// 示例 1： 
//
// 输入：[1,1,1,2,2,2]
//输出：[2,1,2,1,2,1]
// 
//
// 示例 2： 
//
// 输入：[1,1,1,1,2,2,3,3]
//输出：[1,3,1,3,2,1,2,1] 
//
// 
//
// 提示： 
//
// 
// 1 <= barcodes.length <= 10000 
// 1 <= barcodes[i] <= 10000 
// 
//
// 
// Related Topics 堆 排序 
// 👍 59 👎 0
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size();
        vector<int> res;
        map<int,int> count;
        priority_queue<pair<int,int>> queue;

        for (auto num : barcodes)
            count[num]++;

        for(auto p : count){
            queue.push(make_pair(p.first,p.second));
        }

        while(queue.size() >= 2){
            auto p1 = queue.top();
            queue.pop();
            auto p2 = queue.top();
            queue.pop();

            res.push_back(p1.second);
            res.push_back(p2.second);

            if (--p1.first > 0) queue.push(p1);
            if (--p2.first > 0) queue.push(p2);
        }

        if (queue.size() > 0){
            res.push_back(queue.top().second);
        }

        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
